[CERC2017] Buffalo Barricades
考虑算出每个点最终被哪个矩形包含,这种情况下只有相互交叉的两个矩形可能存在覆盖关系。
此时交叉在
因此按矩形的
set 维护的实际上是这样一个结构:
1----.2|3--------.4|5-----------.6|
最终导致的结果,应当是端点在当前线之前的射线,编号都比当前线小。那么考虑一个点属于的矩形,就是覆盖这个点的那条射线。
考虑这样计算,只存在一种情况的矩形没办法准确计算答案,就是矩形
考虑最后加入的矩形,答案一定是正确计算的。而一个没有被正确计算答案的矩形一定较早出现。
按照加入顺序倒序遍历所有矩形,那么找到在最终图形上,包含掉这个矩形的矩形,这只有一个,把答案合并到这上面即可。
xxxxxxxxxx4412const int CN = 6e5 + 10;3using namespace std;4int read(){5 int s = 0, ne = 1; char c = getchar();6 for(; c < '0' || c > '9'; c = getchar()) if(c == '-') ne = -1;7 for(; c >= '0' && c <= '9'; c = getchar()) s = (s << 1) + (s << 3) + c - '0';8 return s * ne;9}10class PAIR{11 public: int x, y;12 bool operator < (const PAIR &o) const {return x ^ o.x ? x < o.x : y < o.y;}13 bool operator == (const PAIR &o) const {return x == o.x && y == o.y;}14} ; set<PAIR> S;15PAIR mp(int a, int b) {PAIR o; o.x = a, o.y = b; return o;}16int n, q, ans[CN], fa[CN], cnt[CN], to[CN], id[CN], X[CN], Y[CN], tp[CN];17bool cmp(int i, int j) {return X[i] ^ X[j] ? X[i] > X[j] : tp[i] > tp[j];}18int fd(int x) {return fa[x] ^ x ? fa[x] = fd(fa[x]) : x;}19int main(){20 freopen("_in.in", "r", stdin);21 n = read(); for(int i = 1; i <= n; i++) X[i] = read(), Y[i] = read(), id[i] = i;22 q = read(); for(int i = n + 1; i <= n + q; i++) X[i] = read(), Y[i] = read(), tp[i] = i - n, id[i] = i;23 sort(id + 1, id + n + q + 1, cmp);24 for(int p = 1, i; i = id[p], p <= n + q; p++){25 if(tp[i]){26 PAIR cur = mp(Y[i], tp[i]); S.insert(cur);27 set<PAIR> :: iterator it = S.find(cur); it++;28 if(it != S.end()) to[tp[i]] = (*it).y;29 it--; while(it != S.begin() && (*--it).y > tp[i]) S.erase(it), it = S.find(cur);30 }31 else{32 PAIR cur = mp(Y[i], 0);33 set<PAIR> :: iterator it = S.lower_bound(cur);34 if(it != S.end()) cnt[(*it).y]++;35 }36 }37 for(int i = 1; i <= q; i++) fa[i] = i;38 for(int i = q; i; i--){39 int x = fd(i), y; ans[i] = cnt[x];40 if(to[i]) y = fd(to[i]), cnt[y] += cnt[x], fa[x] = y;41 }42 for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);43 return 0;44}[HNOI2018] 排列
注意这个限制并不等价于反串的字典序最大!!能转化到字典序模型需要一个“绝对优势”。
考虑一段序列
反过来的话,代价是:
对于确定的树形拓扑序,如果可以比较两个段哪个放在前面更好的话,一种通用的贪心方式就是每次找到最优的那个段,把它往父亲合并。
这样就有复杂度
扩展 KMP 复习
求
定义
直接向后暴力更新就是
xxxxxxxxxx101for(int i = 2, l = 0, r = 0; a[i]; i++){ // 枚举 a 的每个后缀2 if(i <= r) z[i] = min(z[i - l + 1], r - i + 1);3 while(i + z[i] <= la && a[i + z[i]] == a[z[i] + 1]) z[i]++;4 if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;5}6for(int i = 1, l = 0, r = 0; b[i]; i++){ // 枚举 b 的每个后缀7 if(i <= r) g[i] = min(z[i - l + 1], r - i + 1);8 while(i + g[i] <= lb && b[i + g[i]] == a[g[i] + 1]) g[i]++;9 if(i + g[i] - 1 > r) l = i, r = i + g[i] - 1;10}.
[CF780F] Axel and Marston in Bitland & [NOI2020] 美食家
考虑构造矩阵
考虑转移矩阵就是邻接矩阵
考虑一次美食节,等价于第
max+ 矩阵乘法满足结合律,但是没有交换律,最终的转移矩阵形式是
这样朴素做是
考虑直接 DP 的复杂度是
特殊性质 A 非常好做,这样应该就有 75pts。
如果对每个点新建五个点,就是
因为最终结果只需要第一行,如果我们始终维护一个
预处理
[CODE FEST 2016 Grand Final] Water Distribution
对于一个块考虑,它最后整体的和一定是所有点权减掉用过的所有边权,那么最大化这个东西显然需要最小化用过的边权和,那么可以发现这个就是 MST 的边权和。
对每个可能的块预处理,复杂度
最后需要若干个块拼起来,这个直接就
[51nod 1832] 后序与先序遍历
一棵二叉树如果某个节点只有一个儿子,那么无论这个儿子是它的左儿子或者右儿子,这棵树的先序遍历和后序遍历都是不变的。
先序遍历中
设只有一个儿子的节点数量为
[51nod 1231] 记分牌
竞赛图的一个得分合法,等价于对所有
[CF1303F] Number of Components
考虑如果正着做,唯一无法用并查集处理的问题是断掉两个联通块。
如果把这个过程反过来看,又相当于合并两个联通块,因此正反都做一遍即可。
细节???
.
高斯消元求自由元
[POJ1830] 开关问题
考虑按每个变量列方程,然后高斯消元,判断每个方程的主元是否存在即可求出自由元数量。
在实现上,由于可能无法消元成恰好的对角线矩阵,因此需要倒着枚举变量,回代方程。
[HAOI2018] 反色游戏
考虑有
求解
定义一个指针
如果找不到,那么显然
这样我们可以得到一个近似的上三角矩阵,其中第
然后考虑回代过程,那么先枚举无效方程,此时方程右边的系数必须为
然后倒序枚举有主元的方程,我们总能解出该方程的主元的取值,然后向上回代即可。
这样就有 60pts。
xxxxxxxxxx101int equ(){2 int p = 1, ans = 1;3 for(int i = 1; i <= m; i++){4 if(del[i]) continue; int q = p; while(q <= n && !a[q][i]) q++;5 if(q > n) {ans = add(ans, ans); continue;} swap(a[p], a[q]);6 for(int j = p + 1; j <= n; j++) if(a[j][i]) a[j] ^= a[p]; p++;7 }8 for(int i = p; i <= n; i++) if(a[i][m + 1]) return 0;9 return ans;10}[HAOI2018] 染色
设
答案是:
显然有:
那么:
构造
随便 reverse 即可
[Gym - 102978B] Bit Operation
考虑等价于每次选相邻的两个点,然后删掉其中一个。
枚举最后保留下来的点是哪个,那么考虑前后的点必须删掉,显然这个的方案数只和序列长度相关。
考虑枚举最后一次操作删掉了哪个点,如果当前长度为
考虑最后前后的操作序列,只需要考虑相对顺序不变来拼接,有组合数系数
LGV 引理
在一张 DAG 上,有
如果这张 DAG 具备特殊性质,满足有且仅有一种双射能找到合法解,定义邻接矩阵
.
[NOI2018] 你的名字
考虑如果询问是整串,那么我们只需要用
考虑每次跳
如果询问不是整串,那么只需要知道,某条树边是否存在。只需要维护这条边到达节点的
[HAOI2018] 字串覆盖
考虑这样一个新的问题:给定串
考虑建立广义前缀树,找到
xxxxxxxxxx7012using namespace std;345const int CN = 1e5 + 10;6int read(){7 int s = 0, ne = 1; char c = getchar();8 for(; c < '0' || c > '9'; c = getchar()) if(c == '-') ne = -1;9 for(; c >= '0' && c <= '9'; c = getchar()) s = (s << 1) + (s << 3) + c - '0';10 return s * ne;11}12int n, q, pos[CN], pb[CN], len[CN << 2], nxt[CN << 2], fa[20][CN << 2], son[CN << 2][26], idx; char S[CN], T[CN];13void ins(char ch[], bool tp){14 for(int i = 1, u = 0, c; c = ch[i] - 'a', ch[i]; i++){15 if(!son[u][c]) son[u][c] = ++idx; u = son[u][c];16 if(tp) pos[i] = u; else pb[i] = u;17 }18}19int et(int p, int c){20 int u = son[p][c]; if(len[u]) return u; len[u] = len[p] + 1, p = nxt[p];21 while(p ^ -1 && !son[p][c]) son[p][c] = u, p = nxt[p];22 if(p == -1) return u; int d = son[p][c];23 if(len[d] == len[p] + 1) return nxt[u] = d, u;24 int v = ++idx; len[v] = len[p] + 1, nxt[v] = nxt[d], nxt[d] = nxt[u] = v;25 for(int i = 0; i < 26; i++) if(len[son[d][i]]) son[v][i] = son[d][i];26 while(p ^ -1 && son[p][c] == d) son[p][c] = v, p = nxt[p];27 return u;28}29class PAIR {public: int x, y;}; queue<PAIR> Q;30PAIR mp(int a, int b) {PAIR o; o.x = a, o.y = b; return o;}31void bd(){32 for(int i = 0; i < 26; i++) if(son[0][i]) Q.push(mp(0, i));33 while(!Q.empty()){34 int u = Q.front().x, c = Q.front().y; Q.pop(), u = et(u, c);35 for(int i = 0; i < 26; i++) if(son[u][i]) Q.push(mp(u, i));36 }37}38int rt[CN << 2], ch[CN * 70][2], cnt[CN], id[CN << 2], sidx; bool d[CN * 70];39void md(int &u, int l, int r, int p){40 if(!u) u = ++sidx; if(l == r) return (void)(d[u] |= 1);41 int m = (l + r) >> 1; p <= m ? md(lc, l, m, p) : md(rc, m + 1, r, p);42 d[u] = d[lc] | d[rc];43}44int mg(int x, int y, int l, int r){45 if(!(x * y)) return x + y; int u = ++sidx, m = (l + r) >> 1;46 d[u] = d[x] | d[y]; if(l == r) return u;47 lc = mg(ch[x][0], ch[y][0], l, m), rc = mg(ch[x][1], ch[y][1], m + 1, r);48 d[u] = d[lc] | d[rc]; return u;49}50int qu(int u, int l, int r, int s, int t){51 if(!d[u]) return 0; if(l == r) return l; int m = (l + r) >> 1, tmp;52 if(s <= m) {tmp = qu(lc, l, m, s, t); if(tmp) return tmp;}53 return m < t ? qu(rc, m + 1, r, s, t) : 0;54}55int main(){56 nxt[0] = -1, scanf("%s%s", S + 1, T + 1), n = strlen(S + 1), ins(S, 1), ins(T, 0), bd();57 for(int i = 1; i <= n; i++) md(rt[pos[i]], 1, n, i);58 for(int i = 1; i <= idx; i++) cnt[len[i]]++; for(int i = n; i; i--) cnt[i] += cnt[i + 1];59 for(int i = 1; i <= idx; i++) id[cnt[len[i]]--] = i;60 for(int p = 1, i; i = id[p], p <= idx; p++) if(nxt[i]) rt[nxt[i]] = mg(rt[nxt[i]], rt[i], 1, n);61 memcpy(fa[0], nxt, sizeof(nxt)), fa[0][0] = 0;62 for(int k = 1; k < 20; k++) for(int i = 1; i <= idx; i++) fa[k][i] = fa[k - 1][fa[k - 1][i]];63 q = read(); while(q--){64 int l = read(), r = read(), s = read(), t = read(), u = pb[t];65 for(int k = 19; k + 1; k--) if(len[fa[k][u]] >= t - s + 1) u = fa[k][u];66 if(t - s > r - l) puts("0");67 else printf("%d\n", max(0, qu(rt[u], 1, n, l + t - s, r) - t + s));68 }69 return 0;70}那么只需要每次暴力寻找下一个即是
[HAOI2018] 奇怪的背包
需要注意到一个非常重要的事情:所有有效数字都应当是
首先把
直接对着
[HAOI2018] 苹果树
给点第
考虑枚举
答案是:
应该可以卷积。
[JSOI2019] 节日庆典
我们知道对于最小表示法问题,有一个
这样做就是
先考虑一个错误的贪心:取字典序最小的后缀。这个贪心的错因在于接上前缀之后,字典序可能会变大,但是这启发我们,有用的后缀是字典序最小的那些后缀。
形式化地,我们定义一个后缀
可以发现,如果相邻的两个有用的后缀中,后面那个到前面那个的距离小于后面的串长,那么后面的那个没有用处。这说明了有用的后缀数量是
考虑维护有用的后缀构成的集合
考虑由
然后再集合中新增
考虑如何计算前缀
因此复杂度
.
[CF547E] Mike and Friends
考虑类比两个串的做法,先建立广义前缀树,那么一次询问相当于是问某个子树内,线段树上一个区间里面所有出现次数的和。
乍一看这是个二维的东西,考虑有一维是没用的,能不能减少一维。
这样定义线段树:
那么依然可以线段树合并来更新,然后就没了,但是空间怎么算都不够用。
有一个利用 fail 树性质的做法:
先对所有串建立 AC 自动机,维护出每个串的接受状态。考虑将答案差分,变成询问在一个前缀内,某个串在其它串中的出现次数,那么只需要用 AC 自动机顺序读入每个串,将节点上的贡献
时间复杂度
考虑这个题的启发是:
那么:
[SRM550, R1 div1] Conversion Machine
考虑先把
考虑剩下部分走的总步数,设为
设剩下部分还要走
考虑一个抽象的问题模型:
用
种颜色涂长为 的序列,记有 个格子涂上了第 种颜色,则需要满足 ,问有多少种不同的序列。两个序列不同,当且仅当某个位置涂上的颜色不同。
考虑对每种颜色构造 EGF,即
考虑单位根反演,那么
那么答案就是
可以
注意到
.
[NOIAC D1 A] 异或
证明:
首先有取等的条件是 trivial 的,对于
如果
如果
如果
如果
那么判断一个集合合法,只需要将其排序即可。
设
那么一个组里面只能不选,选一个或者选两个,算出每组的方案数相乘即可。
选两个的时候,相当于求有多少数,和一个数异或
特殊情况是
xxxxxxxxxx13123int rt, ch[CN * 60][2], sz[CN * 60], idx;4void ins() {}5int qu(int u, int dep, LL x, LL y){ // ai ^ x <= y6 if(dep < 0) return sz[u];7 if((y >> dep) & 1){8 if((x >> dep) & 1) return qu(lc, dep - 1, x, y);9 return qu(rc, dep - 1, x, y);10 }11 if((x >> dep) & 1) return sz[lc] + qu(rc, dep - 1, x, y);12 return sz[rc] + qu(lc, dep - 1, x, y);13}.
[NOIAC D2 A] 矩阵填数
一个
考虑如果限制矩形均不相交,那么答案很容易计算。
考虑如果两个
先只考虑
如果只有一种
考虑把这两种做法合并起来,那么考虑先算出这种
考虑难求出的东西是一个集合覆盖的总面积
复杂度
Manacher 复习
Manacher 和扩展 KMP 算法有着异曲同工之妙,都是维护一些特殊结构,然后达到均摊
Manacher 用于求出字符串某个位置的回文半径,定义为
对于偶数串
Manacher 维护一个当前找到的右边界最靠右的回文子串
扩展 KMP 用于求出一个串
维护当前找到的右端点最靠右的一段 Border
最长回文前后缀这种东西还是回文树吧...
.
[CF573E] Bear and Bowling
那么考虑一个 naive 的 DP:设
设
[HDU3306] Another Kind of Fibonacci
考虑
这样就可以维护了。也就是说维护乘积求和的时候要试图找乘积的递推关系。
维护
特征方程复习
对于一阶递推
设
那么
对于
设它的两个特征根是
使用前两项解出系数即可。
[HDU2256] Problem of Precision
首先求
我们知道
而
那么
那么答案就是
树状数组上倍增
树状数组的
[联合省选2020 A] 冰火战士
考虑先把两个数组都升序排序,以下做法基于该结论讨论:
找到最后一个满足
考虑如果倍增一个温度
BIT 上倍增即可
灵光一现
求两个字符串
基环树的 Prufer 序列构造
每次找到编号最小的一个叶子,把它的父亲加入序列。如果它的父亲在环上,那么不删除;否则删除这个父亲。
那么可以发现,树上点
如果这个时候已经确定了环的形态,那么就可以确定这个基环树。这里的形态指的是有哪些点,以及点的顺序。
注意一个大环没办法用这种构造表出,或者说表出的结果是空序列 + 大环。
[Code FEST 2017 R3 J] Unicyclic Graph Counting
给定
直接 DP 对推广的 Prufer 序列计数,维护
注意
毒瘤
树是简单图,因此不能有自环或者重边。
先枚举一个环长,构造上面的序列,有:
.
同余最短路
你一开始在
设
设
考虑对每个
[WC2016] 论战捆竹竿
显然等价于一个模型:一开始在
显然
不会了/kk
reflect
线段树合并的时候,判断要这样写:
xxxxxxxxxx11if(!u || !v) return u | v;不要用乘积!!乘积会溢出,很可能被对着卡!!
[THUSCH2017] 大魔法师
先把信息写成向量的形式,然后通过矩阵来进行变换。
考虑 1 操作,相当于乘上
考虑 2 操作,相当于乘上
考虑 3 操作,相当于乘上
考虑 4 操作,相当于加上
考虑 5 操作,相当于乘上
考虑 6 操作,相当于先乘
矩阵的运算满足结合律和分配律,因此维护乘法和加法标记即可。
具体来讲,维护当前区间的值是
循环展开,然后做乘法
当构造函数被调用很多次而可以特判取代时,不写构造也能减少常数。
.
[ZJOI2013] K大数查询
二分一个
考虑分类的过程, 我们只需要把
注意线段树需要还原,复杂度
[AGC001 E] BBQ Hard
考虑即是求
考虑求前面一个柿子,
考虑对整体递推,就是把每个
Border 的四种求法
Periodicity Lemma 指出了周期之间是存在联系的,这个联系基于一个基本事实:周期的倍数依然是周期。
存在结论:
当
当
根据上面的推导,不难发现反过来也是成立的:
也就是说一个串的 Border 和一个串的周期是本质相同的集合,在表现上形成互补的关系。
[HDU3746] Cyclic Necklace
求整串的最短周期,相当于求串的最长 Border,直接 KMP 即可。
[WC2019 Lecture] 周期串查询
求
即求最小周期,是下面这道题的弱化版。直接求出所有 runs,那么答案相当于一个矩形前缀求最小,直接离线二维数点即可。
[BJWC2018] Border 的四种求法
.
[Gym102978H] Harsh Comments
有
考虑 min-max 容斥,那么就枚举一个子集
可以把这个子集看成一个整体,设权值和是
方便起见权值记
这里
对 A 的前后缀做两遍背包,
考虑先做出背包
总复杂度
矩阵转置与转置原理
[bzoj3583] 杰杰的女性朋友
一张
对于任意两个点
可以发现转移矩阵就是
长度恰好为
答案就是
处理
然后对
.
训练 31 订正
B.
考虑直接点分治,然后维护前缀李超树,时间复杂度
考虑如果是序列问题,就直接
考虑先把询问按照重链剖分的 dfs 序划分成
考虑把
李超树两个
A.
考虑即相当于有一些点,一些只能往左走,一些只能往右走, 一些没有限制,求
考虑一个非状压的 DP,设
考虑当前
.
C.
考虑用 LCT 维护森林,然后两个子树合并的时候,现在的并集应该等于两个部分的大小加起来,然后减掉交集。
考虑这个交集,实际上就是上一次合并时这两两个连通块的并集,因为显然新加入的元素不可能有交。
于是直接拿 LCT 维护每棵树的答案,合并分裂都解决了,每次分裂的时候,在这条边上记录一下现在的并集大小即可。
复杂度
.
[雅礼集训 2017 Day1] 字符串
考虑直接每次询问单独做,然后对
注意到
B. Replicate Replicate Rfplicbte
[CF 1276F] Asterisk Substrings
把需要统计的串划分成六类
考虑所有前缀,最后一个字符替换成
考虑对于 endpos 相同的
考虑 set 启发式合并,就是
一些后缀的本质不同前缀数量,等于这些后缀在后缀树上对应节点到根的链长并。实际上可以直接求 dfs 序,然后按照这个启发式合并。
梳理一下做法,先同时建立前缀树和后缀树,然后先算前面五个部分的答案。搞出后缀树的 dfs 序和欧拉序,然后处理出
最小回文划分
只需要考虑对最长回文后缀应用 WPL 即可。
设
考虑设
只需要用
xxxxxxxxxx161void clr() {nxt[0] = len[0] = -1, lst = idx = 1;}2int p = lst, c = ch[i] - 'a';3while(ch[i - len[p] - 1] ^ ch[i]) p = nxt[p];4if(!son[p][c]){5 son[p][c] = ++idx, len[idx] = len[p] + 2;6 int pp = nxt[p]; while(pp ^ -1 && ch[i - len[pp] - 1] ^ ch[i]) pp = nxt[pp];7 nxt[idx] = pp ^ -1 ? son[pp][c] : 1;8 di[idx] = len[idx] - len[nxt[idx]];9 lk[idx] = di[idx] ^ di[nxt[idx]] ? nxt[idx] : lk[nxt[idx]];10}11lst = son[p][c], n++, f[i] = 2e9;12for(int j = lst; j > 1; j = lk[j]){13 g[j] = f[i - len[lk[j]] - di[j]];14 if(di[j] == di[nxt[j]]) g[j] = min(g[j], g[nxt[j]]);15 f[i] = min(f[i], g[j] + 1);16}注意这里
[CF 932G] Palindrome Partition
如果
xxxxxxxxxx31A : abcd2B : abcd3C : ad bc cb da
考虑
那么相当于求
[CF 906E] Reverses
考虑一个 naive 的 DP,设
由于 DP 数组有单调性(错的!),所以求最小的
考虑两个对应位置的子串反转其中一个会相等,就等价于两个子串插起来之后得到的是一个偶回文串。
求最小偶回文划分即可。
.
[CF590E] Birthday
一眼秒了。
先建出 fail 树,显然一个串的子串是它在 fail 树上的祖先。我们希望不存在偏序关系,等价于求 fail 树的最长反链,也就是传递闭包后的最小链覆盖。
就左边建一排点,右边建一排点,每个点向源 / 汇的流量都是 1,然后右点向左点连
求方案?
考虑求出拆点二分图的最大独立集,具体操作是:
从每个没有匹配的左部点开始 dfs,左->右的边只走没有匹配的边,右->左的边只走匹配的边,然后所有 dfs 到的左部点和未 dfs 到的右部点就组成了最大独立集,左右都在最大独立集里的点
[CF700E] Cool Slogans
前缀树上的最长链?有一个问题是,转移时应不应当加一。
如果父节点在子节点中出现了两次以上的话,就应该加一。否则可以把父节点替换成这个点,然后不加一。
线段树合并即可。
坑点:转移的时候需要维护出现在这个节点实际上是哪个点,因为可能不选择这个节点。
坑点:必须从树根往下 DP,因为倒过来的过程可能有多种不同的选择,但是从上向下只有一种选择。
[HDU5390] Tree
可持久化 Tire 的带修只能类似于线性基带修那样,线段树分治来解决。
一个序列带修可持久化 Tire 的在线想法:按序列位置线段树分治,然后一个元素持续存在的位置是一段前缀,它会被拆分成
或者换句话说,对集合(强调无序性)建立的可持久化结构,有一个通用的带修方法。因为本质上这类问题相当于“给一些元素,每个元素在
这个问题有一个通用解决办法就是,把一个元素在线段树上划分成
这样做的空间复杂度是
通常理解的线段树分治相当于对时间轴可持久化,本质上还是解决上面的模型。
实际上是两种角度!!一种角度是用 BIT 那样的单层结构实现可持久化结构,另一种角度是用线段树或分块那样的多层结构实现可持久化结构。
本质上分块是三层线段树!!
考虑原问题,首先想到可以树上可持久化 Tire,但是没有树上 BIT 所以无法支持修改,这样不行。
因为所有查询路径都是从根出发的,这种情况下用不着树链剖分!!树链剖分解决的是任意两个特殊点之间,路径查询的问题。如果一个端点固定,可以被 dfs 序完美代替,因为这个时候另一个点的影响区间在 dfs 序上一定是连续的!!
考虑拿多层 DS 维护。一个元素的影响范畴是它的子树。对 dfs 序建立线段树,然后线段树上每个节点维护一个 Tire,就可以支持在线修改和查询,时空复杂度
考虑可以对线段树上每个节点维护一个 set,里面存所有操作中覆盖到这个区间的元素,按出现时间排序。然后可以只维护一棵 Trie,对每个节点单独做一遍 RMQ,时间
回文树的双端插入和后端删除
双端插入:同时维护两个指针
[HDU5421] Victor and String
从前后段插入字符,询问本质不同的回文串数量和所有回文串数量。
本质不同回文串的数量是回文树的节点数。所有回文串的数量是
xxxxxxxxxx151int nxt[CN], len[CN], son[CN][26], lstl, lstr, pl, pr, idx;2void clr(){3 for(int i = 0; i <= idx; i++) memset(son[i], 0, sizeof(son[i])), nxt[i] = len[i] = 0;4 nxt[0] = len[0] = -1, lstl = lstr = idx = 1;5}6void ins(int &lst, int c, int i, int tp){7 int p = lst; while(ch[i + tp * (len[p] + 1)] ^ ch[i]) p = nxt[p]; 8 if(!son[p][c]){9 son[p][c] = ++idx, len[idx] = len[p] + 2; int pp = nxt[p];10 while(pp ^ -1 && ch[i + tp * (len[pp] + 1)] ^ ch[i]) pp = nxt[pp];11 nxt[idx] = pp ^ -1 ? son[pp][c] : 1, ed[idx] = ed[nxt[idx]] + 1;12 } 13 lst = son[p][c], ans += ed[son[p][c]]; 14 if(len[lst] == pr - pl + 1) lstl = lstr = lst; // border case!15}一种不基于势能分析的插入算法:维护一个转移数组
考虑更新
注意如果
这样时空复杂度都是
在 Trie 上建立回文树 / 末端删除:可以发现后者完全是前者的子问题,而前者可以通过上面的算法简单实现。
当然了
类似的处理办法还出现在了 KMP 自动机中。本质上这的确是一类自动机,只不过没有起始状态和接受状态。
[HDU5394] Trie in Tina Town
就是上面的模板。
xxxxxxxxxx221/* 2to[u][c] 表示如果 u 后面新增一个字符 c, 跳 nxt 的执行结果 3在递归子节点之前把子节点的 to[] 更新成正确的值即可4*/5int len[CN], nxt[CN], lst[CN], son[CN][26], to[CN][26], idx;6void dfs(int u, int dep){7 for(int k = hd[u]; k; k = E[k].nxt){8 int v = E[k].to, c = E[k].c, p = lst[u]; ch[dep] = c;9 if(ch[dep - len[p] - 1] ^ ch[dep]) p = to[p][c];10 if(!son[p][c]){11 son[p][c] = ++idx, len[idx] = len[p] + 2; int pp = nxt[p];12 if(pp == -1) nxt[idx] = 1; 13 else{14 if(ch[dep - len[pp] - 1] ^ ch[dep]) pp = to[pp][c];15 nxt[idx] = son[pp][c];16 }17 memcpy(to[idx], to[nxt[idx]], sizeof(to[nxt[idx]]));18 if(dep > len[nxt[idx]]) to[idx][ch[dep - len[nxt[idx]]]] = nxt[idx];19 }20 lst[v] = son[p][c], dfs(v, dep + 1);21 }22}.
[LOJ517] 计算几何瞎暴力
考虑一次排序之后,下一次排序之前,这个数组每时每刻都可以被划分成两个部分:前面一部分是有一定顺序的,后面一部分则按照加入顺序排列。
考虑这一段之间内,前面那一部分,一定是先是升序的,然后某次 4 操作之后,变成了无序的。但是不考虑这次 4 操作,依然是升序的。如果我们给 4 操作打一个 lazy tag,那么这部分就是升序的。
考虑分开维护,前面一部分拿一个 Trie 维护,询问相当于求前
1 操作,直接接在后面那部分。
2 操作,前后分开询问。后面的前缀和是正确的,前面的需要对 Trie 上每个节点维护
3 操作,后面的前缀和拆位更新,然后整体打一个异或 tag
4 操作,把 Trie 树的整体 tag
复杂度
[CF963D] Frequency of String
考虑长度不同的串只有
于是就 set 启发式合并然后直接做了。
[CF587F] Duff is Mad
先建 fail 树。考虑一个串的所有出现位置是它在 fail 树中的子树。
把询问差分:问
考虑从
考虑按串长分块,考虑串长
[NEERC2015] Distance on Triangulation
考虑对于三角剖分的一条边,它左边部分的点集是
然后我们就可以找一条边使得左右两边分的尽量均匀,然后从这两个点开始广搜,然后分治下去计算。
形式化的理解,相当于在维诺图(对偶图?)上边分治,因为这里维诺图一定是一棵树,可以简单证明。
考虑怎样建立维诺图,就只需要找度数为
每删掉一条边的时候,把当前的点个边上的点连起来。
slstxdy
给定一个点
数据保证任意三个点不共线。
不会做/kk
.
组合数系:任意一个正整数
[LOJ6055] 一道数学题
首先解递推式,得到通项是
错位相减:
有时候错位相减会减不出东西来,但是碰上没有求和方法的柿子要往这方面想!!
如果求和式中包含组合数,那么错位相减大概率可以成功。如果求和式中包含指标的定次幂,那么应该先展开一下搞出组合数。
这样所有的
考虑一行第二类斯特林数可以直接拿通项公式卷积,这样就是大常数
关于错位相减的总结:
朴素做应该可以
插值!
[LOJ6608] 无意识的石子堆
考虑先确定列的分配,再确定行的分配。枚举
答案是
首先只需要强制所有盒子都不为空,然后插板,就能满足接近所有限制。唯一不满足的限制是一个盒子里面的小球必须异色。
根据二项式反演,恰没有盒子使得小球同色的方案数等于钦点
那么这里就是
卷积即可,这样就是
[LOJ6289] 花朵
考虑直接有多大力就多大力 DP,复杂度
考虑如果是一个菊花,只有两种可能:选根,其它的全不选;不选根,其它的随便选。然后分治 FFT 一下,总共 52pts。
考虑如果没有摘掉的节点不相邻这个限制的话,相当于一个广义背包,可以直接分治 FFT 解决掉。
相邻不选的 DP 方程也可以写成卷积!这样来做,设
答案就是
那么一条链也做完了,这样有 67pts.
生成函数的乘法是可以交换的,考虑链分治,把树剖成若干链,然后按照 dfs 序的倒序处理每一条链。先遍历一遍,把链上每个点在这个时候真实的多项式求出来,然后对整条链带权分治 FFT。
考虑这样做什么时候会有优化作用:每次处理一条链的时候,每个节点的多项式大小尽量均匀。容易发现多项式大小和子树大小是相关的,因此选用重链剖分,这样会使得每个点在乘到根的过程中,只出现在
[AGC005F] Many Easy Probs
考虑
考虑所有点对路径都不经过这个点,等价于只能在挖掉这个点之后的若干联通块里面选择。于是贡献和是
考虑对
这里直接把
这样就直接卷积。
.
[LG P5824] 十二重计数法
[CF1096G] Lucky Tickets
首先题目就是让我们求的就是
构造
好像不是很能这样转化....因为有时候,两个系数带权乘起来加起来可能是相等的。或者换句话说,有
那就按照朴素的思路来,构造
求幂:设
也就是
比较系数得
有效的
[PKUWC2018] 猎人杀
对于一个整体,它出现在 1 之前或之后的概率与其它元素是毫无关系的,只跟这个整体的权值和和 1 的权值有关。
考虑算“某个集合里的所有元素均在 1 之前出现”的概率并不好算,因为分母每时每刻都是在变的,这时候我们不能把这些元素当做一个整体。
但是反过来,算某个整体均出现在 1 之后的概率十分好算,这个时候答案实际上就是
于是我们考虑容斥,钦点一个点集
这样可以像二项式反演那样按照集合大小分类,也就是设
然后想到可以直接按照集合的和来分类,设
剩下的问题是处理
这个可以按照区间内
枚举子集容斥的容斥系数和是可以背包,并且可以写出生成函数的!!这一点一定要记清楚。
[XXI Opencup GP of Tokyo H] Harsh Comments
有
考虑 min-max 容斥,相当于对所有 A 物品的集合
这个时候物品分两类,一类在集合
答案是
首先
处理出不包含
这个可以背包,考虑新加入一个元素,所有集合的系数同时乘
相当于乘上一个生成函数
复杂度
.
[CF755G] PolandBall and Many Other Balls
白给好题
有
考虑先选出连续两个的放置方案,相当于求
然后再选出连续一个的放置方案,发现没法卷积...
考虑对于
发现还是没法卷积...
考虑
可以钦点前面有
处理下降幂即可,一次卷积
D5 A
定义积性函数
考虑贡献法,实际上答案是
.
D6 B
如果行列式的某行或者某列有公因子,可以把它提出来计算。
矩阵和它的转置的行列式相等。
考虑答案即是
提公因子得:
可以发现这里每行都是关于
提
考虑按照
D6 C
先考虑怎样选出一个 LIS 等于序列最大值
记住上面两种方法!!选最前面的那个作为代表点,剩下的部分的方案数实际上可以表示出来!!
考虑枚举
可以发现这是一个对
显然后面
考虑所有情况下,每个数字不能出现的段长的和一定是相等的!这可以通过交换位置问题不变来理解。所以前面部分每个数字出现次数也是相等的。
换句话说,当
这样朴素做就是
.
[CF643G] Choosing Ads
区间严格众数有个简单做法:线段树每个节点维护一个二元组
设
注意区间众数和区间带修众数是一个莫队问题。
[ARC093D] Dark Horse
首先
考虑
枚举一个
考虑能和
这样就是
[CF708E] Stu Camp
考虑一个状态数是
显然可以优化,设
设
维护
复杂度
[雅礼集训 2018 Day4] Magic
考虑一个 naive 的 DP,设
考虑每种颜色的卡的使用数量已经确定,那么给卡标号,这样每种颜色的卡可区分,最后答案除
设
考虑
设
对
.
[CF1349F2] Slime and Sequences
草,某题居然是原题
考虑枚举序列最大值
考虑对于确定的
因此这个时候贡献是
不一样!!比如 2 3 1 2 这样也是合法的。
考虑容斥,设
考虑一个好序列 1 2 1 3 4 5 4,可以顺序写下每个数字出现的位置 (1, 3) (2) (4) (5,7) (6),我们发现题目限制等价于第
这样我们建立了从排列到好序列的双射,由此也不难知道好序列的总数一定是
一个数字
显然有性质
也就是每个
边界是
有
可以考虑每个位置的贡献!枚举数字
这样处理欧拉数和计算答案都是
口胡证明是构造一个从排列到序列的映射,但是细节上出了点小问题。具体数学上好像有个代数证明。
考虑求一行欧拉数,设
[LOJ6271] 生成树求和
考虑先拆位
考虑由于是不进位加法,最后的结果一定是
设结果是
那么只考虑计算
很可惜模数没有单位根,考虑
注意基尔霍夫矩阵是度数矩阵减掉邻接矩阵,这里
[ARC096C] Everything on It
考虑容斥,钦点
注意有
考虑组合意义,前面是“先从
就是
[CF1295F] Good Contest
考虑将值域按照区间的起点化成若干段。比如
设
转移系数是
.
训练 34 C
考虑一个简单问题,给定一个序列
考虑对每个右端点
往上套区间查询??
训练 34 B
考虑先建出广义 SAM,然后拿 SAM 读入一个串
也就是说,我从每个读入位置向上暴力跳链,跳过的位置不跳,这样的复杂度是
考虑每次向上覆盖颜色,实际上是等价于一个 access,然后就是树点涂色这个题,直接大力树剖覆盖难写的跟 shi 一样。
考虑拿 LCT 维护这个东西,实链存一些点到根之间的同色段,然后一次修改就直接大力 access 改上去,拿个数组差分解决这个东西,就是
训练 34 A
考虑如果斜率都知道,那么这题就做完了,然后爆搜就是 50pts.
考虑如果按照
一个向量有两个可能的
[CF618E] Robot Arm
线段树维护一些向量形如
错了。一次修改不止改了一个向量,应该是一个后缀的所有向量做旋转笛卡尔系。
每次以
把一个系内的向量,以坐标系为参考,逆时针旋转
也就是
所以直接后缀打矩阵 tag 即可。
[AGC034F] RNG and XOR
min-max 容斥。
考虑先算选出
那么子集反演:
以上均可以高维前缀和处理,复杂度
错了!这么算不对,再 min-max 容斥一遍也不对!列方程是啥东西啊/kk
.
35 A
考虑把一个串合并到它的最小循环节上面去,然后剩下的串数实际上就是答案。也就是说,要求最小循环节等于本串的数的个数。
考虑长度为
还有一个小问题,就是长度为
也就是有转移
狄利克雷卷积暴力计算的复杂度就是
设
然后发现这类似于高维前缀和,可以用每个素数单独转移,复杂度就是
先枚举维数,然后从小到大枚举数字,做前缀和。注意必须从小到大,实际上就是这个维度上的前缀和。
整理一下三种变式:
xxxxxxxxxx21for(int i = 1; i <= p[0]; i++) for(int j = 1; j * p[i] <= n; j++) 2 f[j * p[i]] = add(f[j * p[i]], f[j]);xxxxxxxxxx21for(int i = 1; i <= p[0]; i++) for(int j = n / p[i]; j; j--) 2 f[j * p[i]] = add(f[j * p[i]], P - f[j]);这个好像不能做/kk
后面两个是半在线的,注意区分一下。
35 C
冷静一下,发现需要求
第一个和第三个都很好求,考虑第二个。
第一种思路是对
第二种思路是拿
[CF1264D2] Beautiful Bracket Sequence
考虑给定一个括号串,如何求它的深度。实际上就是找一个间隔,使得间隔左边的左括号个数等于间隔右边的右括号个数,然后答案就是间隔左边的左括号个数。
那么直接 DP,设
考虑实际上不需要 DP,枚举一个位置
换下枚举指标,实际上等于:
.
幂级数的收敛域和收敛半径:zhihu
等比级数的闭合形式,亦即数列
这个还是记住吧...
求逆方式 zhihu:将单位矩阵拼在
行列式为零等价于有一行没有主元,这个可以直接在高斯消元的时候判断。
36 B
考虑递推式:
边界是
显然矩阵求逆随便解决任何
考虑这种二元递推关系,把它表示称复数的形式
好了因为这个优雅的性质,这题可以用另一种途径做,因为
这是有限情况,其中
无限情况下,有闭合形式
级数收敛等价于上式虚部收敛,等价于
如果
另一个点,求
xxxxxxxxxx51Func Sum(a, n){ // sum_{i=0...n-1} a^i2 if(!n) return 13 if(!(n & 1)) return (1 + a) * Sum(a, n >> 1)4 return 1 + (a + a * a) * Sum(a, n >> 1)5}复杂度严格单
36 C
考虑给出一条链,求有多少个三元组
考虑分块,每
因此这样复杂度就是
依然很卡常。
.
一个串的本质不同子串数量就是
但是暴力跳
NOI OL A
数列:0110100110010110...
的分布规律是,popcount(x)%2=1 的位置是某种数字,popcount(x)%2=0 的位置是另一种数字。
还需要一个结论:
考虑一个 60pts 的做法,设
这样可以
考虑设
注意这里 0/1 恰好反转。然后就能拼出答案了。
预处理
对于
.
NOIO / NOIP 答辩题选做
[NOIO2021TG A] 愤怒的小 N
设
前面是自然数幂和问题:
预处理
考虑后面,考虑一个分治的过程,即从高向低枚举
设
设考虑左边界是
注意到当
这样实际上只有
[NOIO2021TG C] 岛屿探险
考虑如果
建立可持久化 Trie,然后讨论:
考虑如果
可以枚举使得
答案就是插入
这样就有大概 55pts.
考虑线段树分治,先离线询问挂在线段树上,那么每个节点都是整段询问,把它们按照
然后对每个节点单独做,就是直接把
.
[HDU5390] Tree
总结下拿线段树分治解决可持久化问题的思路。
这道题首先树剖,然后询问拆成
最后拿一棵 Trie 去遍历线段树结构,不需要可持久化,直接枚举询问,顺序执行操作序列,复杂度
树剖常数小,大力松一松。
[LG P5807] Which Dreamed It
有向图的欧拉回路存在当且仅当每个点的入度等于出度。几个计数定理:
这里欧拉图指存在欧拉回路的图,默认不允许存在空点。两条欧拉回路不同,当且仅当经过边形成的环旋转不同构。
无向图的基尔霍夫矩阵是“每个点相邻边的权值和矩阵”减去边权邻接矩阵。
有向图类似:如果要算外向树,那么相邻边只统计入边;否则只统计出边。
模数是质数!!1
[JSOI2018] 战争
首先存在两个三角形有交就一定存在两个四边形有交....然后等价于两个凸包有交。
考虑求凸包
那么可行的
上面这个结论指出了这个凸包上的点数是
考虑如何求出这个凸包,可以发现这个凸包就是把两个凸包上的边极角排序之后顺次连接起来。先把两个凸包都用向量表示,然后把向量合起来极角排序,定义象限序为“四 < 一 < 二 < 三”然后排序,然后维护出和凸包横坐标最小的那个点,然后按照排序后的向量转一圈就求出来了。
考虑如何判断一个点在凸包内部,找到这个点横坐标处的上凸壳上的边和下凸壳上的边即可,然后叉积随便搞搞。
写麻烦了......
定义点的大小是先按
求闵可夫斯基和可以直接维护出两个凸包的一圈点,然后归并。凸包上的第一个点一定是
判断一个点在凸包内部,可以把凸包上所有点和查询点都减去第一个点的坐标。这样凸包上所有点在一个半平面内且按照极角序排列,可以直接二分找到现在查询点在哪一个三角剖分里面,就可以判断了。
注意可以在凸包后面多留一个点(也就是第一个点)来避免 border case。
xxxxxxxxxx401class POI{2 public: LL x, y;3 POI operator + (const POI &o) const {POI r; r.x = x + o.x, r.y = y + o.y; return r;}4 POI operator - (const POI &o) const {POI r; r.x = x - o.x, r.y = y - o.y; return r;}5 LL operator * (const POI &o) const {return x * o.x + y * o.y;}6 LL operator ^ (const POI &o) const {return x * o.y - y * o.x;}7 bool operator < (const POI &o) const {return x ^ o.x ? x < o.x : y > o.y;}8} a[CN], b[CN], c[CN], stk[CN]; int n, m, q, top;9POI P(int x, int y) {POI r; r.x = x, r.y = y; return r;}10bool cmp(POI a, POI b) {return (a ^ b) > 0;}11void bd(POI a[], int &n){12 sort(a + 1, a + n + 1), top = 0;13 for(int i = 1; i <= n; i++){14 while(top > 1 && ((stk[top] - stk[top - 1]) ^ (a[i] - stk[top])) < 0) top--;15 stk[++top] = a[i];16 }17 for(int i = n - 1; i; i--){18 while(top > 1 && ((stk[top] - stk[top - 1]) ^ (a[i] - stk[top])) < 0) top--;19 stk[++top] = a[i];20 }21 n = top - 1; for(int i = 1; i <= n; i++) a[i] = stk[i];22}23void work(){24 c[top = 1] = a[1] + b[1], a[n + 1] = a[1], b[m + 1] = b[1]; 25 int i = 1, j = 1;26 while(i <= n || j <= m){27 if(j > m || (i <= n && ((a[i + 1] - a[i]) ^ (b[j + 1] - b[j])) > 0))28 c[top + 1] = c[top] + (a[i + 1] - a[i]), i++, top++;29 else c[top + 1] = c[top] + (b[j + 1] - b[j]), j++, top++;30 }31 n = top - 1;32 for(int i = 1; i <= top; i++) a[i] = c[i] - c[1];33 // for(int i = 1; i <= top; i++) printf("%d %d\n", c[i].x, c[i].y);34}35void qu(int x, int y){36 POI cur = P(x, y) - c[1]; int pos = upper_bound(a + 2, a + n + 1, cur, cmp) - a - 1;37 if(pos < 1 || pos > n) return 0;38 if(((cur - a[pos]) ^ (a[pos + 1] - a[pos])) <= 0) return 1;39 return 0;40}.
争取字数破 3w!
38 B
现在有
考虑维护最简形式的线性基,然后加入一个向量。因为我们只需要对每个 1 所在的位置,确定这个位置是否有主元;如果没有,则确定主元并向上下消元。
确定主元一共只会进行
考虑判断有解,当且仅当所有未插入线性基的方程消元结束之后等号右边是零。
这一类复杂度可以这样分析:一共有
这样在线维护比离线高斯消元的复杂度要优。
结论:任意一个八个方块的子矩形,如果都满足外围格子去掉四个角的异或和是零,那么就可以。
38 A
首先我们求所有情况下,从
考虑对着最短路树 DP,设
标号重分配!!!
考虑压状态,选择一个出现次数比较小,影响比较小的变量,然后对这个变量的所有求和一起 DP。这里选择
后面不好处理,再添加状态,设
边界是
[LG P4195] 扩展BSGS
之前想到过为什么适用性会和模数的素性有关,当时感性的给出了一个解释,现在看来好像犯了一个傻.....
重新理性推导一遍。BSGS 基于这个等价转换:
证明是显然的,只需要满足
等价于:
既然是必要的那么只需要检验一下就可以解决充分性问题。还有一个问题是模数的倍数无法区分,这个只需要把数字改写成
玄学,弃了。
.